//单链表：单向 不带头 非循环
public class SingleNode {
    //链表的结点的两个变量值
    public int val;
    public SingleNode next;

    //构造方法
    public SingleNode() {
    }

    public SingleNode(int val) {
        this.val = val;
    }

    //重写toString方法
    @Override
    public String toString() {
        return val + " " + ((next != null) ? next : "") ;

    }

    //头节点引用
    public SingleNode head;

    //节点的构造：调用方法创建5个节点
    public  void creatNode(){

        SingleNode node1 = new SingleNode(12);
        SingleNode node2 = new SingleNode(23);
        SingleNode node3 = new SingleNode(34);
        SingleNode node4 = new SingleNode(45);
        SingleNode node5 = new SingleNode(56);

        //赋值节点值:1 -> 2 -> 3 -> 4 -> 5
        head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

    }

    //打印节点的值
    public void display(){
        SingleNode cur = head;
        System.out.print(this.getClass() + " = [");
        while(cur != null){
            if(cur.next != null)
                System.out.print(cur.val + ",");
            else
                System.out.print(cur.val);
            cur = cur.next;
        }
        System.out.println("]");
    }

    //头插法：在头部位置增加节点
    public void firstAddNode(int val){
        //1.创建一个节点对象
        SingleNode node = new SingleNode(val);
        //2.将创建的节点的next赋值为head
        node.next = this.head;
        //3.将head赋值为node
        this.head = node;
    }

    //尾插法：在末尾加入一个节点
    public void lastAddNode(int val){
        //1.创建一个节点
        SingleNode node = new SingleNode(val);
        //2.没有元素
        if(this.size() == 0){
            head = node;
        }
        //3.存在元素
        //3.1查找最有一个元素
        SingleNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        //该节点的next
        cur.next = node;
    }

    //检测位置是否合法
    private boolean checkPosWhetherLegal(int pos){
        if(pos < 0 || pos > size()) return true;
        return false;
    }

    //指定位置前插入节点
    public void insertBefore(int pos,int val){
        //1.检查位置是否合法
         if(checkPosWhetherLegal(pos))
             throw new PosException("位置非法，不可在此位置前插入：" + pos);
         //2.头插
        if(pos == 0)
            this.firstAddNode(val);
        //3.尾插
        if(pos == size())
            this.lastAddNode(val);
        //4，中间插入
        SingleNode node = new SingleNode(val);
        //查找前一个元素
        SingleNode cur = head;
        for (int i = 1; i < pos; i++) {
            cur = cur.next;
        }
        //赋值
        node.next = cur.next;
        cur.next = node;
    }

    //删除首次的出现元素
    public void remove(int val){
        SingleNode cur = head.next;
        SingleNode tem = head;

        if(size() == 0){
            System.out.println("链表节点为空，不可移除！");
            return;
        }
        if(size() == 1 && head.val == val){
            head = null;
        }
        if(size() != 1 && head.val == val){
            head = head.next;
        }
        //循环遍历
        while(cur != null){
            //找到了，移除
            if(cur.val == val && cur.next == null){
                tem.next = null;
                return;
            }
            if(cur.val == val){
                tem.next = cur.next;
                return;
            }
            tem = tem.next;
            cur = cur.next;
        }
    }

    //将指定元素全部删除
    public void allRemove(int val){
        SingleNode cur = head;
        while(cur != null){
            if(cur.val == val){
                remove(val);
            }
            cur = cur.next;
        }
    }

    //求节点的个数大小
    public  int size(){
        int count = 0;
        SingleNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //判断是否存在某个元素
    public boolean contain(int val){
        SingleNode cur = head;
        while(cur != null){
            if(cur.val == val) return true;
            cur = cur.next;
        }
        return false;
    }

    //回收链表
    public void clear(){
        head = null;
    }
}
